package listnode.question;
/**
 * 题目:
      题意：删除链表中等于给定值 val 的所有节点。
      示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
 * 方法:
      ①直接使用原来的链表来进行删除操作。
      ②设置一个虚拟头结点在进行删除操作。
 */


import listnode.ListNode;

/**
        * Definition for singly-linked list.
        * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 *
 // 法一
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
class RemoveElement {
    public ListNode removeElements(ListNode head, int val) {
     //移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
     //所以头结点其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
        while(head!=null&&head.val==val){// 注意这里不是if
            head=head.next;
        }
        ListNode node=head;
        while(node!=null&&node.next!=null){
            if(node.next.val==val){
                node.next=node.next.next;
            }else{
                node=node.next;
            }
        }
        return head;
    }
}*/

/**
 * 方法二:设置虚拟头结点
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
class RemoveElement {
    public ListNode removeElements(ListNode head, int val) {
        // 设置一个虚拟的头结点
        ListNode dummy=new ListNode();
        dummy.next=head;

        ListNode cur=dummy;
        while(cur.next!=null){
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;//不用head是因为head可能在过程中已经被删掉
    }
}